# 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 
# 
#  求在该柱状图中，能够勾勒出来的矩形的最大面积。 
# 
#  
# 
#  示例 1: 
# 
#  
# 
#  
# 输入：heights = [2,1,5,6,2,3]
# 输出：10
# 解释：最大的矩形为图中红色区域，面积为 10
#  
# 
#  示例 2： 
# 
#  
# 
#  
# 输入： heights = [2,4]
# 输出： 4 
# 
#  
# 
#  提示： 
# 
#  
#  1 <= heights.length <=10⁵ 
#  0 <= heights[i] <= 10⁴ 
#  
# 
#  Related Topics 栈 数组 单调栈 👍 2857 👎 0
from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        length = len(heights)
        left = [-1] * length
        right = [length] * length
        stack = []
        maxs = -1

        for i in range(length):
            while stack and heights[i] < heights[stack[-1]]:
                index = stack.pop()
                # 设置heights[index]的右边界为heights[i],弹出来的是大的，也就是index，小的是i。所以，left数组的第n个元素，他的有边界就是它的值
                right[index] = i
            stack.append(i)

        stack.clear()

        # 找左边小于当前的第一个
        for i in range(length - 1, -1, -1):
            while stack and heights[i] < heights[stack[-1]]:
                index = stack.pop()
                # 设置heights[index]的左边界为heights[i]
                left[index] = i
            stack.append(i)

        # print(d)
        for i in range(length):
            maxs = max(maxs, ((right[i] - left[i] - 1) * heights[i]))
        return maxs


# leetcode submit region end(Prohibit modification and deletion)
print(Solution().largestRectangleArea(heights=[2, 1, 5, 6, 2, 3]))
